package com.yoshino.leetcode.interview150.heap;

import java.util.PriorityQueue;

class MedianFinder {

    PriorityQueue<Integer> ltMid;
    PriorityQueue<Integer> gtMid;
    public MedianFinder() {
        // 存比中位数小的
        ltMid = new PriorityQueue<>((a, b) -> b - a);
        // 存比中位数大的
        gtMid = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // 为空，比中位数小的
        if (ltMid.isEmpty() || num <= ltMid.peek()) {
            ltMid.add(num);
            if (gtMid.size() + 1 < ltMid.size()) {
                gtMid.add(ltMid.remove());
            }
        } else {
            gtMid.add(num);
            if (gtMid.size() > ltMid.size()) {
                ltMid.add(gtMid.remove());
            }
        }
    }
    
    public double findMedian() {
        if (ltMid.size() > gtMid.size()) {
            return ltMid.peek();
        }
        return (ltMid.peek() + gtMid.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */